package explore.hxx.binarytree.self;

import explore.hxx.binarytree.dependence.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author waxijiang
 */
public class MidOrderTraversal {
    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        node.left = null;
        node.right = new TreeNode(2);
        node.right.left = new TreeNode(3);
        node.right.right = null;

        System.out.println(midOrderTraversal(node));
    }

    /**
     * 中序遍历
     *
     * @param root 树根
     * @return 中序遍历列表
     */
    public static List<Integer> midOrderTraversal(TreeNode root) {
        // 定义辅助空间
        List<Integer> result = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        // 排除特殊情况
        if (root == null) {
            return result;
        }

        TreeNode tmp = root;
        do {
            while (tmp != null) {
                // 获取栈顶
                // 如果该根节点的左节点为null则表示该节点左树遍历结束
                stack.push(tmp);
                // 中序遍历左树
                tmp = tmp.left;
            }

            // 节点的左树中序遍历结束后，遍历根节点
            if (!stack.isEmpty()) {
                tmp = stack.pop();
                result.add(tmp.val);
                // 然后中序遍历右子树
                tmp = tmp.right;
            }

        } while (tmp != null || !stack.isEmpty());

        return result;
    }
}
